#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

template <class T>
struct Less{
  bool operator()(const T& left, const T& right)
  {
    return left < right;
  }
};

template <class T>
struct Greater{
  bool operator()(const T& left, const T& right)
  {
    return left > right;
  }
};

template <class T, class Compare>
void insert_sort(vector<T> &vc, Compare comp = Less<T>()){
  for(int i = 0; i <vc.size()-1; ++i)
  {
    int end = i;
    T x = vc[end+1];
    while(end >= 0)
    {
      if(comp(x, vc[end]))
      {
        vc[end+1] = vc[end];
        --end;
      }
      else{
        break;
      }

    }
    vc[end+1] = x;
  }
}

template <class T, class Compare>
void shell_sort(vector<T> &vc, Compare comp){
  int gap = vc.size();
  while(gap > 1)
  {
    gap = gap/3+1;
    for(int i = 0; i<vc.size()-gap; ++i)
    {
      int end = i;
      T x = vc[end+gap];
      while(end >= 0)
      {
        if(comp(x, vc[end]))
        {
          vc[end+gap] = vc[end];
          end-=gap;
        }
        else{
          break;
        }
      }
      vc[end+gap] = x;
    }
  }
}

//template <class T, class Compare>
//void select_sort(vector<T> &vc, Compare comp){
//  for(int i = 0; i < vc.size()-1; ++i)
//  {
//    int tmp  = i;
//    for(int j = i+1; j < vc.size(); ++j)
//    {
//      if(comp(vc[j], vc[tmp]))
//      {
//        tmp = j;
//      }
//    }
//    swap(vc[i], vc[tmp]);
//  }
//}

template <class T>
void select_sort(vector<T> &vc){
  int left = 0;
  int right = vc.size()-1;
  while(left < right)
  {
    int maxi = left;
    int mini = left;
    for(int i = left+1; i<=right; ++i)
    {
      if(vc[i] < vc[mini])
      {
        mini = i;
      }
      if(vc[i] > vc[maxi])
      {
        maxi = i;
      }
    }
    swap(vc[left], vc[mini]);
    if(left == maxi)
    {
      maxi = mini;
    }
    swap(vc[right], vc[maxi]);
    ++left;
    --right;
  }
}

template <class T, class Container = vector<T>, class Compare = Less<T>>
class heap{
  Container _con; 
  Compare comp;
public:
  template <class InputIterator>
  heap(InputIterator first, InputIterator last){
    while(first != last)
    {
      _con.push_back(*first);
      ++first;
    }
    for(int i = (size()-2)/2; i >= 0; --i)
    {
      adjust_down(i);
    }
  }

  void push(const T& val){
    _con.push_back(val);
    adjust_up(size()-1);
  }

  void pop(){
    swap(_con[0], _con[size()-1]);
    _con.pop_back();
    adjust_down(0);
  }

  const T& top(){
    return _con[0];
  }

  void adjust_up(int child){
    int parent = (child-1)/2;
    while(child > 0)
    {
      if(comp(_con[parent], _con[child]))
      {
        swap(_con[parent], _con[child]);
        child = parent;
        parent = (child-1)/2;
      }
      else{
        break;
      }
    }
  } 

  void adjust_down(int parent){
    int child = parent*2+1;
    while(child < size())
    {
      if(child+1<size() && comp(_con[child] , _con[child+1]))
      {
        ++child;
      }
      if(comp(_con[parent], _con[child]))
      {
        swap(_con[parent], _con[child]);
        parent = child;
        child = parent*2+1;
      }
      else{
        break;
      }
    }
  }

  bool empty(){
    return _con.empty();
  }

  size_t size(){
    return _con.size();
  }

};

template <class T, class Compare>
void adjust_down(vector<T>& vc, Compare comp, int size, int parent){
  int child = parent*2+1;
  while(child < size)
  {
    if(child+1<size && comp(vc[child] , vc[child+1]))
    {
      ++child;
    }
    if(comp(vc[parent], vc[child]))
    {
      swap(vc[parent], vc[child]);
      parent = child;
      child = parent*2+1;
    }
    else{
      break;
    }
  }
}

template <class T, class Compare>
void heap_sort(vector<T>& vc, Compare comp = Less<T>()){
  for(int i = (vc.size()-2)/2; i >= 0; --i)
  {
    adjust_down(vc, comp, vc.size(), i);
  }

  for(int end = vc.size()-1; end > 0; --end)
  {
    swap(vc[0], vc[end]);
    adjust_down(vc, comp, end, 0);
  }
}

template <class T, class Compare>
void bubble_sort(vector<T>& vc, Compare comp = Less<T>()){
  int end = vc.size()-1;
  while(end > 0)
  {
    bool exchange = false;
    for(int i = 0; i < end; ++i)
    {
      if(comp(vc[i+1], vc[i]))
      {
        exchange = true;
        swap(vc[i+1], vc[i]);
      }
    }
    if(!exchange)
    {
      break;
    }
    --end;
  }
}

